#  跳跃游戏 II
# 题目保证可以到达 nums[n-1]
from typing import List


def jump(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums_length = len(nums)
    # 特殊情况考虑
    #
    current_index = 0
    min_step = 0
    while current_index < nums_length - 1:
        # 当前位置无法继续往下跳，无解
        current_count = nums[current_index]
        if current_count <= 0:
            return 0

        # 这个循环用来判断调到哪一步的性价比最高，从 current_index 开始跳，主要是用来计算 next_index
        # 默认是调到下一个位置
        temp = 1 + nums[current_index + 1]
        next_index = current_index + 1
        for count in range(2, current_count + 1):
            # 避免越界
            if current_index + count < nums_length:
                if current_index + count == nums_length - 1:
                    next_index = current_index + count
                    break
                elif count + nums[current_index + count] >= temp:
                    temp = nums[current_index + count] + count
                    next_index = current_index + count

        # 跳一步
        current_index = next_index
        min_step += 1
    return min_step


def jump_1(nums: List[int]) -> int:
    ans = 0
    cur, nxt = 0, 0
    while nxt < len(nums) - 1:
        ans += 1
        tmp = nxt
        for nx in range(cur, nxt + 1):
            tmp = max(tmp, nx + nums[nx])
        cur, nxt = nxt + 1, tmp
    return ans


nums_1 = [1]
result = jump(nums_1)
print(f"result : {result}")

nums_1 = [2, 3, 1]
result = jump(nums_1)
print(f"result : {result}")

nums_1 = [3, 2, 1]
result = jump(nums_1)
print(f"result : {result}")

nums_1 = [3, 2, 1, 0, 4]
result = jump(nums_1)
print(f"result : {result}")

nums_1 = [1, 2, 3, 4, 5]
result = jump(nums_1)
print(f"result : {result}")

nums_1 = [1, 1, 1, 1, 4]
result = jump(nums_1)
print(f"result : {result}")
